In [2]:
G = nx.Graph()
G.add_edges_from([(1,2),(2,3), (2,4), (3,4), (1,3)])
nx.draw(G, with_labels=True, )
This handin corresponds to the topics in Week 10-15 in the course.
The handin is
For the handin, you will prepare a report in PDF format, by exporting the Jupyter notebook. Please submit
Submit both files on Brightspace no later than April 21 kl. 11.59PM.
The grading system: Tasks are assigned a number of points based on the difficulty and time to solve it. The sum of the number of points is 100. For the maximum grade you need to get at least 80 points. The minimum grade (02 in the Danish scale) requires at least 30 points, with at least 8 points on of the first three Parts (Part 1,2,3) and 6 points in the last part (Part 4). Good luck!
The exercise types: There are three different types of exercises
np.mean, itertools.combinations, and so on). However, if the task is to implement an algorithm, by no means a call to a library that implements the same algorithm will be deemed as sufficient!### BEGIN IMPORTS - DO NOT TOUCH!
import os
os.environ["KMP_DUPLICATE_LIB_OK"]="TRUE"
import sys
sys.path.append('..')
#!{sys.executable} -m pip install matplotlib
#!{sys.executable} -m pip install networkx
#!{sys.executable} -m pip install torchvision
import random
import scipy.io as sio
import time
import networkx as nx
import numpy as np
%matplotlib inline
import matplotlib.pyplot as plt
import csv
from itertools import count
import torch
import torch.optim
import torch.nn as nn
import torch.nn.functional as F
import torchvision
import torchvision.transforms as transforms
from utilities.load_data import load_mnist
import utilities.email as email
from utilities.mnist import *
from utilities.make_graphs import read_edge_list, read_list, load_data
### END IMPORTS - DO NOT TOUCH!
C:\Users\Simon\Documents\dm2023-exercises\handins
In this exercise recall that the PageRank is defined as
$$\mathbf{r} = \alpha \mathbf{Mr} + (1-\alpha)\mathbf{p}$$where $\mathbf{r}\in \mathbb{R}^n$ is the PageRank vector, $\alpha$ is the restart probability, $\mathbf{M} = A\Delta^{-1}$, and $\mathbf{p}$ is the restart (or personalization) vector.
What is the PageRank of a $d$-regular graph with $n$ nodes and $\alpha=1$?
[Motivate] your answer without showing the exact computation.
$\mathbf{r} = \alpha \mathbf{Mr} + (1-\alpha)\mathbf{p} = 1 \cdot \mathbf{Mr} + (1-1)\mathbf{p} = \mathbf{Mr} = \mathbf{A}\Delta^{-1}r$
The page rank is $\frac{1}{n}$ for all the nodes.
Look at the graph below (run the code) and try make a guess about the PageRank values of each node only by reasoning on the graph's connections.
G = nx.Graph()
G.add_edges_from([(1,2),(2,3), (2,4), (3,4), (1,3)])
nx.draw(G, with_labels=True, )
1: 2/10 2: 3/10 3: 3/10 4: 2/10
A) [Implement] the PageRank for $\alpha=1$ for the graph using the Power Iteration method (use $\epsilon=1e-16$ to stop the iteration).
B) [Implement] Plot the norm square difference of the $r$ vector (between any two consecutive iterations) for each iteration.
C) [Motivate] Do you observe a constant decrease of the norm square difference as iterations are increasing, and is this decrease expected or not?
D) [Implement] the PageRank for $\alpha=1$ using the eigenvector method.
E) [Motivate] Are solutions of both methods the same? Why don't we only use the eigenvector method that optimally solves the problem?
F) [Motivate] Do the real vector match with your first guess? Can you see a pattern between the pagerank score of each node and its edges?
#A) YOUR CODE HERE
# Implement pagerank algorithm given graph G and alpha using the power iteration method and use epsilon = 1e-16 as stopping criterion.
def pagerank(G, alpha):
adjacency_matrix = nx.adjacency_matrix(G)
adjacency_matrix = adjacency_matrix.todense()
A = np.array(adjacency_matrix)
r = np.ones(adjacency_matrix.shape[0])
r = r / r.shape[0]
Delta = [[np.sum(A[i]) if i == j else 0 for j in range(r.shape[0])] for i in range(r.shape[0])]
Delta_inv = np.linalg.inv(Delta)
M = A @ Delta_inv
epsilon = 1e-16
diff = 1
while(diff > epsilon):
r_s = r
r = alpha * M @ r + (1 - alpha) / G.number_of_nodes()
diff = np.linalg.norm(r - r_s)
return r
print(pagerank(G, 1))
[0.2 0.3 0.3 0.2]
#B) YOUR CODE HERE
# Plot the norm square difference of the $r$ vector (between any two consecutive iterations) for each iteration.
def pagerank_plot(G, alpha):
adjacency_matrix = nx.adjacency_matrix(G)
adjacency_matrix = adjacency_matrix.todense()
A = np.array(adjacency_matrix)
r = np.ones(adjacency_matrix.shape[0])
r = r / r.shape[0]
Delta = [[np.sum(A[i]) if i == j else 0 for j in range(r.shape[0])] for i in range(r.shape[0])]
Delta_inv = np.linalg.inv(Delta)
M = A @ Delta_inv
epsilon = 1e-16
diff = 1
diff_list = []
while(diff > epsilon):
r_s = r
r = alpha * M @ r + (1 - alpha) / G.number_of_nodes()
diff = np.sum(pow(r - r_s, 2))
diff_list.append(diff)
return diff_list
diff_list = pagerank_plot(G, 1)
plt.plot(diff_list)
plt.show()
C) Yes, the norm square difference is decreasing as iterations are increasing. This is expected because the norm square difference is the difference between the current r vector and the previous r vector. The difference should decrease as the r vector converges to the correct value.
#D) YOUR CODE HERE
# Implement the PageRank for $\alpha=1$ using the eigenvector method.
def pagerank_eigenvector(G, alpha=1):
adjacency_matrix = nx.adjacency_matrix(G)
adjacency_matrix = adjacency_matrix.todense()
A = np.array(adjacency_matrix)
n = A.shape[1]
v = np.ones(n) / n
M_hat = (alpha * A) + (((1 - alpha) / n) * np.ones((n, n)))
eigvals, eigvecs = np.linalg.eig(M_hat.T)
idx = np.argmax(eigvals)
largest_eigenvector = np.real(eigvecs[:, idx])
return largest_eigenvector / np.sum(largest_eigenvector)
print(pagerank_eigenvector(G))
[0.21922359 0.28077641 0.28077641 0.21922359]
E) No the output of the two methods differ. The first one will only have postive outputs, whereas pagerank with eigenvector does not neccesarily needs to output a positive value. Also the eigenvector method is more accurate than the power iteration method. The power iteration method is not guaranteed to converge to the correct solution. The eigenvector method is guaranteed to converge to the correct solution.
F) I think the real vector matches with my first guess. The pagerank score of each node is the same as the number of edges it has. The node with the most edges has the highest pagerank score.
[Motivate]
Assume you have embedded the graph in 1.1.2 with a Linear Embedding using unormalized Laplacian matrix of the graph as the similarity matrix. How do you expect the embeddings to be if the embedding dimension is $d = 1$? (1) Check the correct box below and (2) motivate your answer.
IMPORTANT: Do NOT just choose one answer. Please clarify WHY this is the correct answer.
When we use the unnormalized Laplacian matrix as the similarity matrix and embed the graph in one dimension, the embeddings will correspond to the eigenvector of the smallest non-zero eigenvalue of the Laplacian matrix. The smallest eigenvalue is 1, and the corresponding eigenvector is $[0.5, -0.5, -0.5, 0.5]$. Therefore, nodes 2 and 3 will have the same embedding, which is $-0.5$, and nodes 1 and 4 will have the same embedding, which is $0.5$. As a result, nodes 1 and 4 will be far from nodes 2 and 3 in the embedding space.
[Prove] the following properties: You will be given points for each of the properties that you prove, rather than points for the exercise as a whole.
Note that all question correspond to the eigenvalues of the LAPLACIAN (NOT THE NORMALIZED)
For a graph with $n$ nodes the eigenvalues of the LAPLACIAN ($L = D - A$) is sorted in ascending order, i.e.,
$\lambda_0\leq\lambda_1\leq...\leq\lambda_{n-1}$
For all graphs $\lambda_0 = 0$
Since it holds for $L$, that: $$ x^T L x = \sum_{(u,v)\in E} (x_u - x_v)^2 $$ and since it is symmetric, it is easy to see, that L is a positive semidefinite matrix. Thus it holds, that all eigenvalues are going to be positive. This implies, that if we can show that there indeed will always exist an eigenvector with a corresponding eigenvalue equal to zero, then the statement $\lambda_0 = 0$ for all graphs is true. If $L$ is an $n \times n$ matrix, then we see that when we multiply L with the vector consisting of only one's:
\begin{align*} L \begin{bmatrix} 1 \ 1 \ \vdots \\ 1 \end{bmatrix} &= D \begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{bmatrix} - A \begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{bmatrix} \\ &= \begin{bmatrix} d_{11} \\ d_{22} \\ \vdots \\ d_{nn} \end{bmatrix} - \begin{bmatrix} \sum_{j=1}^n a_{1j} \\ \sum_{j=1}^n a_{2j} \\ \vdots \\ \sum_{j=1}^n a_{nj} \end{bmatrix} \\ &= \begin{bmatrix} d_{11} \\ d_{22} \\ \vdots \\ d_{nn} \end{bmatrix} - \begin{bmatrix} d_{11} \\ d_{22} \\ \vdots \\ d_{nn} \end{bmatrix} \\ &= 0 \cdot \begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{bmatrix} \end{align*}thus concluding the proof, that the eigenvector consisting of only one's has the eigenvalue $\lambda_0 = 0$, which exists for all graphs.
For the complete graph, $\lambda_1, \dots, \lambda_{n-1} = n$
Let $x_0 = [1, \dots, 1]^T$ be the eigenvector with eigenvalue $\lambda_0 = 0$. For some other eigenvector $x_j$ where $j \in [1, n-1]$, we must have that it is perpendicular with $x_0$. Thus, we see that the inner product implies the following: $$ \sum_{i=1}^n x_j^{(i)} x_0^{(i)} = 0 \implies \sum_{i=1}^n x_j^{(i)} = 0 $$ where $x_j^{(i)}$ denotes the $i$'th entry of vector $x_j$. Then, we have for the complete graph, that: \begin{align*} L x_j &= \begin{bmatrix} (n-1) x_j^{(1)} - \sum_{i eq 1} x_j^{(i)} \\ \vdots \\ (n-1) x_j^{(n)} - \sum_{i eq n} x_j^{(i)} \end{bmatrix} \\ &= (n-1) \begin{bmatrix} x_j^{(1)} - \sum_{i eq 1} x_j^{(i)} \\ \vdots \\ x_j^{(n)} - \sum_{i eq n} x_j^{(i)} \end{bmatrix} \\ &= (n-1) \begin{bmatrix} x_j^{(1)} - \left(\sum_{i} x_j^{(i)}\right) + x_j^{(1)} \\ \vdots \\ x_j^{(n)} - \left(\sum_{i} x_j^{(i)}\right) + x_j^{(n)} \end{bmatrix} \\ &= (n-1) \begin{bmatrix} x_j^{(1)} + x_j^{(1)} \\ \vdots \\ x_j^{(n)} + x_j^{(n)} \end{bmatrix}\\ &= n \begin{bmatrix} x_j^{(1)} \\ \vdots \\ x_j^{(n)} \end{bmatrix}\\ &= n x_j \end{align*} Which shows that for all eigenvectors $x_j$ where $j \in [1, n-1]$, the corresponding eigenvalues will be $\lambda_1 = \lambda_2 = \dots = \lambda_{n-1} = n$
For all the graphs with $k$ connected components $\lambda_0 = \lambda_1 =...=\lambda_ k = 0$
Let the sets $C_1$ to $C_k$ denote all $k$ connected components each containing component indices. Assume without any loss of generality, that the adjacency matrix is segmented nicely; that is, the first rows belongs to one component, the next rows belong to the next component etc. Here's an example of a 'nicely segmented' Laplacian matrix $L$ with 3 components: $$ \begin{bmatrix} 2 & -1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 \\ -1 & 2 & -1 & 0 & 0 & 0 & 0 & 0 & 0 \\ -1 & -1 & 2 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 2 & -1 & -1 & 0 & 0 & 0 \\ 0 & 0 & 0 & -1 & 2 & -1 & 0 & 0 & 0 \\ 0 & 0 & 0 & -1 & -1 & 2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 2 & -1 & -1 \\ 0 & 0 & 0 & 0 & 0 & 0 & -1 & 2 & -1 \\ 0 & 0 & 0 & 0 & 0 & 0 & -1 & -1 & 2 \end{bmatrix} $$ of course if the adjacency matrix is not nicely segmented, then the following idea still works; we just do elementary row operations. Then it holds for any eigenvector $x$, that: $$ \begin{align*} L x &= \begin{bmatrix} (|C_1|-1) x_1 - \sum_{i \in C_1\backslash\{1\}} x_i \\ (|C_1|-1) x_2 - \sum_{i \in C_1\backslash\{2\}} x_i \\ (|C_1|-1) x_3 - \sum_{i \in C_1\backslash\{3\}} x_i \\ \vdots \\ (|C_k|-1) x_n - \sum_{i \in C_k\backslash\{n\}} x_i \\ \end{bmatrix} \end{align*} $$ If we then define $x_1$ as such: $$ x_1 = [\underbrace{1, 1, \dots, 1}_{|C_1|}, \underbrace{0, 0, \dots, 0}_{n-|C_1|}]^T $$ then $$ L x_1 = \begin{bmatrix} (|C_1|-1) - \sum_{i \in C_1\backslash\{1\}} x_i \\ (|C_1|-1) - \sum_{i \in C_1\backslash\{2\}} x_i \\ (|C_1|-1) - \sum_{i \in C_1\backslash\{3\}} x_i \\ \vdots \\ (|C_1|-1) - \sum_{i \in C_1\backslash\{|C_1|\}} x_i \\ 0 \\ \vdots \\ 0 \end{bmatrix} = \begin{bmatrix} (|C_1|-1) - (|C_1|-1) \\ (|C_1|-1) - (|C_1|-1) \\ (|C_1|-1) - (|C_1|-1) \\ \vdots \\ (|C_1|-1) - (|C_1|-1) \\ 0 \\ \vdots \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ \\ \vdots \\ \\ \\ 0 \\ 0 \end{bmatrix} = 0 x_1 $$ By constructing $x_1$ to $x_k$ in this fashion - for instance $x_2$: $$ x_2 = [\underbrace{0, 0, \dots, 0}_{|C_1|},\underbrace{1, 1, \dots, 1}_{|C_2|}, \underbrace{0, 0, \dots, 0}_{n-|C_2|-|C_1|}]^T $$ and since we already know $x_0$ as the vector of ones having eigenvalue equal to zero, we can finally conclude that: $$ \lambda_0 = \lambda_1 = \dots = \lambda_k = 0 $$
Given a graph $G$ with eigenvalues of the laplacian $\lambda_0, \lambda_1,...,\lambda_{n-1}$.
We randomly remove an edge from $G$ and we re-calculate the eigenvalues as $\lambda'_0, \lambda'_1,...,\lambda'_{n-1}$.
Can we have $\lambda'_{i}>\lambda_{i}$ for some $0\leq i\leq n-1$? Why? Why not?
We will prove that:
$$\sum_{i=0}^{n-1} \lambda_i' \leq \sum_{i=0}^{n-1} \lambda_i $$Because eigenvalues are sorted in ascending order, and the fact that any eigenvalue is greater or equal to zero, it follows by the above, that there does $\textbf{not}$ exist an $i$ such that $\lambda_i' > \lambda_i$.
In order to prove the above, note that: \textbf{Lemma 1: For the trace of a symmetric matrix $A$, it holds that $tr(A) = \sum_{i=0}^{n-1} \lambda_i$}
By Lemma 1, we realise that $tr(L) = \sum_{i=0}^{n-1} \lambda_i$. Since removing an edge corresponds to subtracting 1 from $L_{ii}$ and $L_{jj}$ where $i \ eq j$, as the diagonal corresponds to values from the degree matrix; we see that if we remove an edge from $G$ to obtain $L'$, we have that:
$$ tr(L') = tr(L) - 2 $$thus
$$\sum_{i=0}^{n-1} \lambda_i' = \left( \sum_{i=0}^{n-1} \lambda_i \right) - 2 \leq \sum_{i=0}^{n-1} \lambda_i$$which completes the proof, and shows that $\lambda'_{i}>\lambda_{i}$ for some $0\leq i\leq n-1$ can $\textbf{not}$ happen.
Suppose that the graph $G$ consists of two connected componentes of equal size named $G_1$ and $G_2$. For simplicity assume that $n$ is even.
The Laplacian of $G_1$ has eigenvalues $\lambda^1_0,\lambda^1_1,...,\lambda^1_{n/2-1}$.
The Laplacian of $G_2$ has eigenvalues $\lambda^2_0,\lambda^2_1,...,\lambda^2_{n/2-1}$.
Prove that the Laplacian of $G$ is consisted of the eigenvalues of the Laplacians of $G_1$ and $G_2$ in ascending order.
Assume without any loss of generality, that G is in the following form: $$ G = \begin{bmatrix} G_1 & 0 \\ 0 & G_2 \end{bmatrix} $$ Then the Laplacian of G can be written as: $$ L = \begin{bmatrix} L_1 & 0 \\ 0 & L_2 \end{bmatrix} $$ Where $L_1$ and $L_2$ are the Laplacian's of $G_1$ and $G_2$.
Now, let $x^{(i)}$ denote the $i$'th entry of vector $x$. If $x_{L_1}$ is an eigenvector for $L_1$, then $x_L$ is an eigenvector for $L$, where: $$ x_L = [x_{L_1}^{(1)}, x_{L_1}^{(2)}, \dots, x_{L_1}^{(n/2)}, \underbrace{0, 0, \dots, 0}_{n/2}] $$ Likewise, an eigenvector for $L_2$ will be an eigenvector for $L$ where we place zeroes at the beginning instead of at the end: $$ x_L = [\underbrace{0, 0, \dots, 0}_{n/2}, x_{L_2}^{(1)}, x_{L_2}^{(2)}, \dots, x_{L_2}^{(n/2)}] $$ This shows, that all eigenvectors for $L_1$ and $L_2$ will be eigenvectors for $L$. Now we have to determine whether or not the eigenvalues are preserved. We will call $x_L$ as an extended eigenvector by applying the above zero-padding. It is easy to see, that an eigenvector for $L_i$ and the extended eigenvector for $L$, will share the same eigenvalue for $L$ and $L_i$. That is: $$ L_i x = k x\\ L x_L = k x_L $$ Since the eigenvalues are preserved, it follows that the eigenvalues of the Laplacian of G will preserve the eigenvalues of $G_1$ and $G_2$.
In this part, you will experiment and reflect on spectral clustering as a technique for partitioning a graph.
In this subsection you will experiment with some biological data https://journals.plos.org/ploscompbiol/article?id=10.1371/journal.pcbi.1003268.
!IMPORTANT! First run the following code to load the data.
#Load Data
from utilities.make_graphs import read_edge_list, read_list, load_data
import numpy as np
X, Y = load_data()
[Implement] the $\varepsilon$-neighborhood graph, using Eucledian ($L_2$) distance.
Note: Be sure that your constructed graph does not contain self-loop edges (edges from i to i for each i)
#YOUR CODE HERE
# Be sure that your constructed graphs does not
# contain loop edges (edges from i to i for some node i)
def nn_graph(data, eps, remove_self=True, directed=False):
n = len(X)
G = nx.Graph()
if directed:
G = nx.DiGraph()
### YOUR CODE STARTS HERE
G.add_nodes_from(range(n))
L2 = lambda x, y: np.sqrt(np.sum((x - y) ** 2))
dist = [[L2(X[i], X[j]) for j in range(n)] for i in range(n)]
for i in range(n):
for j in range(i + 1, n):
if dist[i][j] < eps:
G.add_edge(i, j)
if remove_self:
G.remove_edges_from(nx.selfloop_edges(G))
### YOUR ENDS CODE HERE
return G
Try with different $\varepsilon$ values (select a small set of $\varepsilon$, e.g., 0.01-0.5 values) and plot the graphs.
[Motivate] what you observe as epsilon increases.
### Run the code below
eps_values = [0.01, 0.05, 0.1, 0.2, 0.4]
for eps in eps_values:
ax=plt.subplot()
ax1=plt.subplot()
G = nn_graph(X, eps)
pos=nx.spring_layout(G)
nx.draw_networkx_edges(G, pos=X)
nx.draw_networkx_nodes(G, pos=X, node_color=Y, node_size=20, cmap=plt.get_cmap('tab10'))
ax.set_xlim(-0.1, 1.1)
ax.set_ylim(-0.1, 1.1)
plt.show()
When $\varepsilon$ increases, the more nodes are being intepreted as adjacent, thus increasing the connectivity of the graph.
Assign to each edge in the $\varepsilon$-neighborhood graph a weight
$$W_{i j}=e^{-\frac{\left\|\mathbf{x}_{i}-\mathbf{x}_{j}\right\|^{2}}{t}}$$[Implement] the function weighted_nn_graph below that returns the weighted graph given the data matrix in input and the values eps and $t$, where $t$ is the parameter of the equation above.
def weighted_nn_graph(data, eps=20, t=0.1):
n = len(data)
G = nx.Graph()
### YOUR CODE STARTS HERE
G.add_nodes_from(range(n))
L2 = lambda x, y: np.sum((x - y) ** 2)
weigh = lambda d : np.exp(-d / t)
dist = [[L2(X[i], X[j]) for j in range(n)] for i in range(n)]
for i in range(n):
for j in range(i + 1, n):
if weigh(dist[i][j]) < eps:
G.add_edge(i, j, weight=weigh(dist[i][j]))
# G.add_edge(i, j)
### YOUR CODE ENDS HERE
return G
Vary $t \in \{10, 0.1, 0.000001\}$. Plot the weights as a histogram using the code below in order to analyse the results using the provided code. What happens when $t$ is very small, close to $0$, i.e., $t \rightarrow 0$? What happens when $t$ is very large? Is the behaviour with $t = 0$ expected?
[Motivate] your answer reasoning on the formula.
ts = [10, 0.2, 0.07, 0.000001]
fig, ax = plt.subplots(1,4, figsize=(20, 10))
row = 0
for i, t in enumerate(ts):
G = weighted_nn_graph(X, eps=60, t=t)
ys = []
col = i
for i, d in enumerate(G.edges.data()):
ys.append(d[2]['weight'])
plt.hist(ys, bins=100)
ax[col].hist(ys, bins=100)
ax[col].set_title("t: "+str(t))
plt.tight_layout()
When $t$ is very small, close to 0, the weight $W_{ij}$ becomes very large for small $\left|\mathbf{x}{i}-\mathbf{x}{j}\right|^{2}$ values. This is because the exponential term in the formula approaches 1 for small values of $\left|\mathbf{x}{i}-\mathbf{x}{j}\right|^{2}$, making the weight almost equal to $\exp(1)\approx 2.718$, which is a very large value. Therefore, for small values of $t$, the weights become very large, leading to a highly connected graph.
On the other hand, when $t$ is very large, the weight $W_{ij}$ becomes very small for all values of $\left|\mathbf{x}{i}-\mathbf{x}{j}\right|^{2}$. This is because the exponential term in the formula approaches 0 for large values of $\left|\mathbf{x}{i}-\mathbf{x}{j}\right|^{2}$, making the weight almost equal to 0. Therefore, for large values of $t$, the weights become very small, leading to a sparsely connected graph.
If we set $t=0$, the weight $W_{ij}$ becomes 1 for all edges, regardless of the distance between the nodes. This is because $e^{-\frac{\left|\mathbf{x}{i}-\mathbf{x}{j}\right|^{2}}{t}}$ approaches 1 as $t$ approaches 0. Therefore, the behaviour with $t=0$ is expected.
We will now look at spectral clustering and its properties.
For this Task we will use a subgraph from malaria_genes.
Note that this dataset is the biological network of the data used in Task 2.1.
Run the code below to load and visualize the network.
By only observing the below plot and the $nn$-plots (nearest-neighbor plots)of task 2.1.2, which $\varepsilon$ values seems to better approximate the real network? (just think of the answer you don't have to write something)
edgelist = read_edge_list('./data/edges.txt')
n = np.max(edgelist)+1
G = nx.Graph()
for i in range(n):
G.add_node(i)
for edge in edgelist:
G.add_edge(edge[0], edge[1])
pos=nx.spring_layout(G)
nx.draw_networkx_edges(G,pos=X)
nx.draw_networkx_nodes(G, pos=X, node_color=Y, node_size=20, cmap=plt.get_cmap('tab10'))
plt.show()
Now you are having the real network, lets check how good $nn$-graph (and for which $\epsilon$ value) is a good "approximates"the real graph.
A) [Implement] a function that calculates the absolute edge difference between the real network $G$ and the one $\epsilon$-neighborhood graph. Note that in order to do that you have to follow two steps:
B) [Implement] Plot the edge-difference plot for the range of epsilon values in the range[0.01, 0.11] with step = 0.005.
C) [Motivate] By observing the plot it seems that there exists only one global minimum and no local minimum. Try to prove/disprove this intuition.
#A) YOUR CODE HERE
def abs_edge_diff(G, nn):
counter = 0
for i, j in G.edges():
if (i, j) not in nn.edges():
counter += 1
for i, j in nn.edges():
if (i, j) not in G.edges():
counter += 1
return counter
G_nn = nn_graph(X, 0.08333)
print(G)
print(G_nn)
print(abs_edge_diff(G, G_nn))
Graph with 307 nodes and 2812 edges Graph with 307 nodes and 2811 edges 2409
#B) YOUR CODE HERE
differences = []
epss = np.arange(0.01, 0.115, 0.005)
for eps in epss:
G_nn = nn_graph(X, eps)
diff = abs_edge_diff(G, G_nn)
differences.append(diff)
plt.plot(epss, differences)
plt.show()
It seems as though there are a global minimum around $\varepsilon = 0.07$. The y value of the curve increases again after $\varepsilon = 0.07$ and converges to a value after x = 1.
The plot is not completely smooth and concave with a clear global minimum in the range specified in the assignment.
Compute the eigenvectors and eigenvalues (using the provided function) of the Normalized Laplacian and the Random Walk Laplacian of the graph $G$.
Plot the spectrum (eigenvalues).
[Implement] the code to compute the different Laplacians.
def graph_eig(L):
"""
Takes a graph Laplacian and returns sorted the eigenvalues and vectors.
"""
lambdas, eigenvectors = np.linalg.eig(L)
lambdas = np.real(lambdas)
eigenvectors = np.real(eigenvectors)
order = np.argsort(lambdas)
lambdas = lambdas[order]
eigenvectors = eigenvectors[:, order]
return lambdas, eigenvectors
L_norm = None
L_rw = None
### YOUR CODE STARTS HERE
identity_matrix = np.identity(len(G.nodes()))
adjacency_matrix = nx.adjacency_matrix(G).toarray()
degree_matrix = np.diag(np.sum(adjacency_matrix, axis=1))
inverse_sqrt_degree_matrix = np.linalg.inv(np.sqrt(degree_matrix))
laplacian_matrix = degree_matrix - adjacency_matrix
L_norm = inverse_sqrt_degree_matrix @ laplacian_matrix @ inverse_sqrt_degree_matrix
L_rw = identity_matrix - (np.linalg.inv(degree_matrix) @ adjacency_matrix)
### YOUR CODE ENDS HERE
eigval_norm, eigvec_norm = graph_eig(L_norm)
eigval_rw, eigvec_rw = graph_eig(L_rw)
plt.figure(0)
plt.plot(eigval_norm, 'b-o', label='Spectrum of Normalized Laplacian', )
plt.legend()
plt.figure(1)
plt.plot(eigval_rw, 'b-o', label='Spectrum of the Random Walk Laplacian')
plt.legend()
<matplotlib.legend.Legend at 0x23c01286c90>
[Implement] the function spect_cluster that returns a vector y_clust in which each entry y_clust[i] represents the community assigned to node $i$. The method should be able to handle both the Normalized Laplacian, and the Random Walk Laplacian. You are allowed to use your implementation from the weekly exercises and sklearn.cluster.k_means for k-means clustering.
from sklearn.cluster import k_means
def spect_cluster(G, eig_type="normal", k=5, d=5):
### YOUR CODE STARTS HERE
identity_matrix = np.identity(len(G.nodes()))
adjacency_matrix = nx.adjacency_matrix(G).toarray()
degree_matrix = np.diag(np.sum(adjacency_matrix, axis=1))
inverse_sqrt_degree_matrix = np.linalg.inv(np.sqrt(degree_matrix))
laplacian_matrix = degree_matrix - adjacency_matrix
L_norm = inverse_sqrt_degree_matrix @ laplacian_matrix @ inverse_sqrt_degree_matrix
L_rw = identity_matrix - (np.linalg.inv(degree_matrix) @ adjacency_matrix)
eigval_norm, eigvec_norm = graph_eig(L_norm)
eigval_rw, eigvec_rw = graph_eig(L_rw)
if eig_type == "normal":
eigvec = eigvec_norm
else:
eigvec = eigvec_rw
y_clust = k_means(eigvec[:, 1:d], k, n_init="auto")[1]
### YOUR CODE ENDS HERE
return y_clust
def plot_graph(G, clusters):
plt.figure(1,figsize=(30,15))
nodes = G.nodes()
ec = nx.draw_networkx_edges(G, X, alpha=0.2)
nc = nx.draw_networkx_nodes(G, X, nodelist=nodes, node_color=clusters, node_size=100, cmap=plt.cm.jet)
plt.axis('off')
plt.show()
your_clusters = spect_cluster(G, k=6)
plot_graph(G, your_clusters)
Finally, use your implementation of spectral clustering with different Laplacians and different values of $k \in [2,7]$ and plot the results using the helper function plot_graph.
[Describe] the results you obtain. Especially, what is the difference between the Random Walk and the Normalized Laplacians, if any? How do you explain such differences?
for method in ['normal', 'random']:
for k in np.arange(2,8):
your_clusters = spect_cluster(G,eig_type=method, k=k)
plot_graph(G, your_clusters)
